package leetcode_core.leetcode_6;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月20日 12:19
 */
public class Exist {
    private int[][] memo;
    private int[][] steps = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    private boolean isFind;
    public boolean exist(char[][] board, String word) {
        //参数校验
        if(board.length == 0 || board[0].length == 0){
            return false;
        }
        int n = board.length,m = board[0].length;
        isFind = false;
        memo = new int[n][m];
        char beginChar = word.charAt(0);
        char[] wordStr = word.toCharArray();
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(board[i][j] == beginChar){
                    memo[i][j] = 1;
                    dfs(new StringBuilder().append(board[i][j]),i,j,n,m,wordStr,1,board,wordStr.length);
                    if(isFind){
                        return true;
                    }
                    memo[i][j] = 0;
                }
            }
        }
        return false;
    }
    private void dfs(StringBuilder path,int x,int y,int n,int m,char[] target,int index,char[][] board,int length){
        if(index == length){
            isFind = true;
            return ;
        }
        for(int k = 0;k<4;k++){
            int tx = x + steps[k][0];
            int ty = y + steps[k][1];
            if(tx <0 || tx >=n || ty<0 || ty>=m){
                continue;
            }
            if(target[index] == board[tx][ty] && memo[tx][ty] == 0){
                path.append(board[tx][ty]);
                memo[tx][ty] = 1;
                dfs(path,tx,ty,n,m,target,index+1,board,length);
                if(isFind){
                    return ;
                }
                memo[tx][ty] = 0;
                path.deleteCharAt(index);
            }
        }
    }



}
